from math import sqrt
import System

# Returns the Pearson correlation coefficient for p1 and p2
def sim_pearson(prefs,p1,p2):
  # Get the list of mutually rated items
  si={}
  for item in prefs[p1].Keys:
    if item in prefs[p2].Keys: 
      si[item]=1

  # if they are no ratings in common, return 0
  if len(si)==0: return 0

  # Sum calculations
  n=len(si)

  # Sums of all the preferences
  sum1=sum([prefs[p1][it] for it in si])
  sum2=sum([prefs[p2][it] for it in si])

  # Sums of the squares
  sum1Sq=sum([pow(prefs[p1][it],2) for it in si])
  sum2Sq=sum([pow(prefs[p2][it],2) for it in si])

  # Sum of the products
  pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])

  # Calculate r (Pearson score)
  num=pSum-(sum1*sum2/n)
  den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
  if den==0: return 0

  r=num/den
  return r


def scaledown(prefs, width, height, distance=sim_pearson,rate=0.01):
  users=prefs.Keys

  realdist = dict(dict([]))
  for i in users:
      realdist.setdefault(i, dict())
      for j in users:
        realdist[i].setdefault(j, 0.0)
        realdist[i][j] = distance(prefs,i,j)
 
  # The real distances between every pair of items
  #realdist=[[distance(prefs,i,j) for j in users]
             #for i in users]

  # Randomly initialize the starting points of the locations in 2D
  random = System.Random()
  loc=dict([(i,[random.Next(width),random.Next(height)]) for i in users])
  fakedist=dict([(i,dict([(j, [0.0 for j in users])])) 
            for i in users])

  lasterror=None
  for m in range(0,1000):
    # Find projected distances
    for i in users:
      for j in users:
        fakedist[i][j]=sqrt(sum([pow(loc[i][x]-loc[j][x],2)
                                 for x in range(len(loc[i]))]))

    # Move points
    grad=dict([(i,[0.0,0.0]) for i in users])

    totalerror=0
    for k in users:
      for j in users:
        if (j==k): continue
        if realdist[j][k] == 0: continue
        if fakedist[j][k] == 0: continue
 
        # The error is percent difference between the distances
        errorterm=(fakedist[j][k]-realdist[j][k])/(realdist[j][k])

        # Each point needs to be moved away from or towards the other
        # point in proportion to how much error it has
        
        grad[k][0]+=((loc[k][0]-loc[j][0])/(fakedist[j][k]))*errorterm
        grad[k][1]+=((loc[k][1]-loc[j][1])/(fakedist[j][k]))*errorterm

        # Keep track of the total error
        totalerror+=abs(errorterm)
    print totalerror

    # If the answer got worse by moving the points, we are done
    if lasterror and lasterror<totalerror: break
    lasterror=totalerror

    # Move each of the points by the learning rate times the gradient
    for k in users:
      loc[k][0]-=rate*grad[k][0]
      loc[k][1]-=rate*grad[k][1]

  return loc